import java.util.HashSet;
import java.util.Set;

/*
 * @lc app=leetcode.cn id=869 lang=java
 *
 * [869] 重新排序得到 2 的幂
 */

// @lc code=start
class Solution {
    static Set<Integer> set = new HashSet<>();
    static {
        for(int i = 1; i < (int)1e9 + 10; i *= 2){
            set.add(i);
        }
    }
    int m;
    int[] cnts = new int[10];
    //dfs 深度优先搜索
    public boolean reorderedPowerOf2(int n) {
        while(n != 0){
            cnts[n % 10]++;
            n /= 10;
            m++;
        }
        return dfs(0, 0);
    }
    boolean dfs(int u, int cur){
        if(u == m){
            //judge if set contains cur, if contains, return true
            return set.contains(cur);
        }
        for(int i = 0; i < 10; i++){
            if(cnts[i] !=0){
                cnts[i]--;
                // 判断 i != 0 避免首数字为0
                if((i != 0 || cur != 0) && dfs(u + 1, cur * 10 + i)){
                    return true;
                }
                cnts[i]++;
            }
        }
        return false;
    }
}
// @lc code=end

